Задача #A0081

Память 16 MB Время 1000 ms Сложность 30 %

#Depth-First Search

#Union Find

Bekatlar

Bitlandiya mamlakatida n ta bekat bor. Ular mos ravishda koordinatalar sistemasida joylashgan. Bir bekatdan ikkinchisiga borish mumkin bo'ladi qachonki ular bitta vertikal yoki gorizantal chiziqda yotgan bo'lsa. BitVoy ning aniqlashicha shunaqa bekatlar bor ekanki ulardan ba'zi bir bekatlarga borishning imkoni yo'q ekan. Shu sababdan Hokim unga eng kam bekatlar qurish orqali barcha bekatlarni bog'lashni buyurdi. Unga bunda yordam bering.

Входные данные:

Kirish faylida birinchi qatorda \(n(1 \le n \le 100)\) bekatlar soni keyingi n ta qatorda har bir bekat koordinatasi kiritiladi x_i va y_i \((1\le x_{i}, y_{i} \le 1000)\) .

Выходные данные:

Chiqish faylida qurilishi kerak bo'lgan minimal bekatlar sonini kiriting.

Примеры

#	input.txt	output.txt
1	2 2 1 1 2	1
2	2 2 1 4 1	0

Telegram Facebook

Отправить решение

Пожалуйста, войдите в систему, чтобы выполнить это действие,если у вас нет учетной записи, вы можете зарегистрироваться в любое время